package Q63;

/**
 * 不同路径2
 * @author 23737
 * @time 2021.11.23
 */
public class Test {
    public static void main(String[] args) {

    }
}

/**
 * dp
 */
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //row
        int row = obstacleGrid.length;
        //column
        int column = obstacleGrid[0].length;

        //define
        int[][] dp = new int[row][column];
        //避免出现最上角的值就是障碍物
        dp[0][0] = 1-obstacleGrid[0][0];
        //init
        for (int i = 1; i < row; i++) {
            if(obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1){
                dp[i][0] = 1;
            }
        }

        for (int i = 1; i < column; i++) {
            if(obstacleGrid[0][i] == 0 && dp[0][i-1] == 1) {
                dp[0][i] = 1;
            }
        }

        //dp
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                if(obstacleGrid[i][j] == 1){
                    continue;
                }
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }

        //result
        return dp[row][column];
    }
}
